/*
 * author: VDaras
 */

#ifndef GRID_H
#define	GRID_H

#include <cstdlib>
#include <exception>
#include <list>

/**
 * Grid spatial data structure.
 */


template <class T>
class Grid
{
private:

    std::list< T > **m_grid;
    unsigned m_rows, m_columns;
    unsigned m_cellWidth, m_cellHeight;

public:

    /**
     * Constructs a grid.
     *
     * @param rows - count of grid's rows
     * @param column - count of grid's columns
     * @param cellWidth - width of the grid's cells
     * @param bucketHeight - height of the grid's cells
     */

    Grid(unsigned rows, unsigned columns, unsigned cellWidth, unsigned cellHeight)
    :
    m_rows(rows),
    m_columns(columns),
    m_cellWidth(cellWidth),
    m_cellHeight(cellHeight)
    {
        m_grid = NULL;

        AllocateCells();
    }

    ~Grid()
    {
        DeallocateCells();
    }

    /**
     * @return grid's row count.
     */

    unsigned GetRows() const
    {
        return m_rows;
    }

    /**
     * @return grid's column count.
     */

    unsigned GetColumns() const
    {
        return m_columns;
    }

    /**
     * @return grid's cell width.
     */

    unsigned GetCellWidth() const
    {
        return m_cellWidth;
    }

    /**
     * @return grid's cell height.
     */

    unsigned GetCellHeight() const
    {
        return m_cellHeight;
    }


    /**
     * @return the total width of the grid. 
     */

    unsigned GetWidth() const
    {
        return m_cellWidth * m_columns;
    }


    /**
     * @return the total height of the grid 
     */

    unsigned GetHeight() const
    {
        return m_cellHeight * m_rows;
    }



    /**
     * Sets the size of the grid's cells.
     *
     * @param cellWidth
     * @param cellHeight
     */

    void SetCellSize(unsigned cellWidth, unsigned cellHeight)
    {
        m_cellWidth = cellWidth;
        m_cellHeight = cellHeight;
    }


    /**
     * Inserts an element to the grid.
     *
     * @param toInsert - element to insert
     * @param x - element's x value
     * @param y - element's y value
     * @return a boolean value indicating if insertion was successful or not.
     */

    bool Insert(const T &toInsert, unsigned x, unsigned y)
    {
        //convert x and y to array indices
        int column = x / m_cellWidth;
        int row = y / m_cellHeight;


        //if the point is out of the grid's bounds
        if(row >= m_rows || column >= m_columns)
        {
            //return failure
            return false;
        }

        //insert element
        m_grid[row][column].push_front(toInsert);

        //return success
        return true;
    }

    /**
     * Returns the cell of the grid with the specified row and column.
     *
     * @param row - desired row
     * @param column - desired column
     * @return a list with the elements that reside within the specified cell
     */

    std::list< T >& At(unsigned row, unsigned column)
    {

        return m_grid[row][column];
    }

    /**
     * Returns a cell by converting the x,y coordinate to a row and a column.
     *
     * @param x
     * @param y
     * @return
     */

    std::list< T >& RelativeAt(unsigned x, unsigned y)
    {
        int row, column;
        CoordinatesToIndices(x, y, row, column);

        return m_grid[row][column];
    }

    /**
     * Converts the coordinates passed to grid incdices.
     *
     * @param x - x coordinate
     * @param y - y coordinate
     * @param row - row corresponding to the y coordinate
     * @param column - column correspond to the x coordinate
     */

    void CoordinatesToIndices(unsigned x, unsigned y, unsigned &row, unsigned &column) const
    {
        column = x / m_cellWidth;
        row = y / m_cellHeight;
    }
    

    /**
     * Returns the total count of the grid's elements.
     */

    int ElementCount() const
    {
        int count = 0;

        for(int i = 0; i < m_rows; ++i)
        {
            for(int j = 0; j < m_columns; ++j)
            {
                count += m_grid[i][j].size();
            }
        }

        return count;
    }
    

    /**
     * Clears all the grid's elements.
     */

    void Clear()
    {
        for(unsigned i = 0; i < m_rows; ++i)
        {
            for(unsigned j = 0; j < m_columns; ++j)
            {
                m_grid[i][j].clear();
            }
        }
    }

private:

    /**
     * Allocates storage for the grid.
     */

    void AllocateCells()
    {
        if(m_grid != NULL)
        {
            DeallocateCells();
        }


        //allocate a 2d array of lists with rows equal to the grid's rows
        //an columns equal to the grid's columns
        m_grid = new std::list< T > * [m_columns];

        for(unsigned i = 0; i < m_columns; ++i)
        {
            m_grid[i] = new std::list< T >[m_rows];
        }
    }

    /**
     * Deallocates the grid's storage.
     */

    void DeallocateCells()
    {
        if(m_grid != NULL)
        {
            for(unsigned i = 0; i < m_columns; i++)
            {
                delete[] m_grid[i];
            }

            delete[] m_grid;
            m_grid = NULL;
        }
    }
};

#endif	/* GRID_H */

